from math import comb, inf  # 组合
from typing import *
from functools import cache
import bisect
from bisect import bisect_left, bisect_right
import random
from random import randint, randrange
from collections import defaultdict  # 1157
from itertools import accumulate
from math import gcd
import heapq
from heapq import heapify, heappop, heappush, heapreplace
from sortedcontainers import SortedSet, SortedDict, SortedList
from cmath import log


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def array2node(head: List) -> ListNode:
    root = node = ListNode()
    for val in head:
        node.next = ListNode(val)
        node = node.next
    return root.next


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


__direction = [[0, 1], [1, 0], [0, -1], [-1, 0]]  # 北，东，南，西


def buildgraph(n, edges: List[List[int]]):
    g = [[] for _ in range(n)]
    for x, y in edges:
        g[x].append(y)
        g[y].append(x)
